5 最长回文子串

https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvn3ke/

cost: NaN

class Solution {
public:
    string longestPalindrome(string s) {
        int maxIdx = 0;
        int maxSize = 1;
        vector<vector<int>> memo(s.size(), vector<int>(s.size(), 0));
        for (int j = 0; j < s.size(); j++) {
            for (int i = j; i >= 0; i--) {
                if (i == j) {
                    memo[i][j] = 1;
                    continue;
                }
                if (j - i == 1 && s[i] == s[j]) {
                    memo[i][j] = 2;
                    if (maxSize < memo[i][j]) {
                        maxSize = memo[i][j];
                        maxIdx = i;
                    }
                    continue;
                }
                if (s[i] == s[j] && memo[i + 1][j - 1] != 0) {
                    memo[i][j] = memo[i + 1][j - 1] + 2;
                    if (maxSize < memo[i][j]) {
                        maxSize = memo[i][j];
                        maxIdx = i;
                    }
                }
            }
        }
        return s.substr(maxIdx, maxSize);
    }
};